package me.mingshan.leetcode;

import java.util.Stack;

/**
 * https://leetcode.cn/problems/sum-of-left-leaves/
 * <p>
 * 给定二叉树的根节点 root ，返回所有左叶子之和。
 *
 * @author hanjuntao
 * @date 2025/8/27 0027
 */
public class L_404_左叶子之和 {


    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);
        System.out.println(sumOfLeftLeaves2(root)); // 24
    }

    /**
     * 思路：
     * <p>
     * 利用栈进行迭代，在判断节点是否是左叶子节点时，累加
     *
     * @param root
     * @return
     */
    public static int sumOfLeftLeaves(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int result = 0;

        Stack<TreeNode> stack = new Stack<>();
        // 根节点入栈
        stack.push(root);

        while (!stack.isEmpty()) {
            // 先打印根节点
            TreeNode pop = stack.pop();

            // 由于栈后入先出，需要先将右子树入栈，再将左子树入栈
            if (pop.right != null) {
                stack.push(pop.right);
            }

            if (pop.left != null) {
                // 如何判断是否左叶子节点呢？
                // 1. 左子树没有子树
                // 2. 左子树没有右子树
                if (pop.left.left == null && pop.left.right == null) {
                    result += pop.left.val;
                }
                stack.push(pop.left);
            }
        }

        return result;
    }

    /**
     * 递归
     *
     * 1. 判断当前节点的左子节点是否是叶子节点，如果是，则累加，否则递归遍历左子树
     * 2. 递归遍历右子树
     *
     *
     * @param root
     * @return
     */
    public static int sumOfLeftLeaves2(TreeNode root) {
       if (root == null) {
           return 0;
       }

       return dfs(root);
    }

    public static int dfs(TreeNode node) {
        int ans = 0;
        if (node.left != null) {
            ans += isLeafNode(node.left) ? node.left.val : dfs(node.left);
        }
        if (node.right != null) {
            ans += dfs(node.right);
        }
        return ans;
    }

    public static boolean isLeafNode(TreeNode node) {
        return node.left == null && node.right == null;
    }

}
